package 力扣链表;

public class Leedcode面试题0205链表求和 {
    public static void main(String[] args) {
        ListNode l1 = new ListNode(0);
//        l1.next = new ListNode(9);

        ListNode l2 = new ListNode(1);
        l2.next = new ListNode(9);

        ListNode node = addTwoNumbers(l1, l2);
        System.out.println(node.val);
        System.out.println(node.next.val);
        System.out.println(node.next.next.val);
    }
    //方法2：递归
    public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        //递归终止条件
        if (l2 == null){
            return l1;
        }
        if (l1 == null){
            return l2;
        }
        ListNode h1 = l1;
        ListNode h2 = l2;
        //我只知道当前两个链表d额头节点的和，剩下的我不知道，交给add方法
        //如果有节点为空，并且temp== 0，直接返回还有节点的链表
        int temp = (h1.val + h2.val ) > 9 ? 1 : 0;
        if (temp == 0){
            h1.val = (h1.val + h2.val );
        }else {//temp = 1;
            h1.val = ((h1.val + h2.val) % 10);
            h1.next = addIsOverTen(h1.next,temp);
        }
        h1.next = addTwoNumbers(h1.next,h2.next);
        return h1;
    }

    //方法1：开辟新空间
    public static ListNode addTwoNumbers1(ListNode l1, ListNode l2) {

        //方法1：创建一个新链表
        ListNode dummy = new ListNode();
        ListNode dummyHead = dummy;
        if (l1 == null){
            return l2;
        }
        if (l2 == null){
            return l1;
        }

        ListNode h1 = l1;
        ListNode h2 = l2;
        int temp = 0;
        while (h1 != null && h2 != null){
            int sum = h1.val + h2.val + temp;
            if (sum > 9){
                temp = 1;
            }else {
                temp = 0;
            }
            dummy.next = new ListNode(sum % 10);
            h1 = h1.next;
            h2 = h2.next;
            dummy = dummy.next;
        }
        //如果有节点为空，并且temp== 0，直接返回还有节点的链表
        if (temp == 0){
            dummy.next = h1 == null ? h2 : h1;
        }else {//temp = 1;
            //判断那个节点为空
            if (h1 == null && h2 == null){
                dummy.next = new ListNode(1);
            }else if (h1 == null){
                dummy.next = addIsOverTen(h2,temp);
            }else {
                dummy.next = addIsOverTen(h1,temp);
            }
        }
        return dummyHead.next;
    }
    public static ListNode addIsOverTen(ListNode head,int temp){
        if (head == null){
            return new ListNode(temp);
        }
        ListNode cur = head;
        if ((cur.val + temp) > 9){
            cur.val = 0;
            temp = 1;
            if (cur.next == null){
                cur.next = new ListNode(1);
            }else {
                addIsOverTen(cur.next,temp);
            }
        }else {
            cur.val += 1;
        }
        return head;
    }
}
